package leetcode_day._2021._202111;

import general_class.Node;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/21 10:19
 * N 叉树的最大深度
 * 给定一个 N 叉树，找到其最大深度。
 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
 * N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
 * 算法：广度优先搜索、深度优先搜索
 */
public class _21_559 {

    public int maxDepthBfs(Node root) {
        if (root == null) return 0;
        Deque<Node> queue = new ArrayDeque<>();
        int ans = 0;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                final Node poll = queue.poll();
                if (poll != null && !poll.children.isEmpty()) queue.addAll(poll.children);
            }
            ++ans;
        }
        return ans;
    }

    public int maxDepthDfs(Node root) {
        if (root == null) return 0;
        int ans = 0;
        for (Node child : root.children) ans = Math.max(ans, maxDepthDfs(child));
        return ans + 1;
    }

}
